﻿<!doctype html>
<html>
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no">

    <title>葡萄藤PPT</title>

    <link rel="stylesheet" href="https://ptteng.github.io/PPT/css/reveal/reveal.css">

    <!-- PPT主题，可以在/css/reveal/theme/中选择其他主题，目前暂时只能使用该模板 -->
    <link rel="stylesheet" href="https://ptteng.github.io/PPT/css/reveal/theme/ptt.css">

    <!-- syntax highlighting 代码高亮主题 -->
    <link rel="stylesheet" href="https://ptteng.github.io/PPT/lib/reveal/css/zenburn.css">
   

    <!-- 打印和PDF输出样式 -->
    <script>
        var link = document.createElement( 'link' );
        link.rel = 'stylesheet';
        link.type = 'text/css';
        link.href = window.location.search.match( /print-pdf/gi ) ? 'https://ptteng.github.io/PPT/css/reveal/print/pdf.css' : '../css/reveal/print/paper.css';
        document.getElementsByTagName( 'head' )[0].appendChild( link );
    </script>
</head>
<body>
<img src="https://ptteng.github.io/PPT/img/demo/logo.png" alt="" usemap="#pttmap" class="base-logo">
<map name="pttmap">
    <area shape="rect" coords="0,0,276,58" href="http://www.jnshu.com" alt="" target="_blank"/>
</map>
<div class="reveal">
    <div class="slides">
	
        <section>
            <h3>洗牌算法具体指的是什么？</h3>
            <p>分享人:冯亚超</p>
        </section>
		
        <section>
            <p>1.背景介绍</p>
            <p>2.知识剖析</p>
            <p>3.常见问题</p>
            <p>4.解决方案</p>
            <p>5.编码实战</p>
            <p>6.扩展思考</p>
            <p>7.参考文献</p>
            <p>8.更多讨论</p>
        </section>
		
        <section>
            <h3>1.背景介绍</h3>
        </section>
		
        <section>	           	
            <p>洗牌算法(Shuffling Algorithm)，顾名思义，它的产生是用来解决类似洗牌这种场景的问题的，目的是产生一串等概率的随机列，使得很难去预测牌的顺序。</p>	
		</section>       
		
		<section>
            <p>什么是好的洗牌算法：</p>
			<p>洗牌之后，如果能够保证每一个数出现在所有位置上的概率是相等的，那么这种算法是符合要求的；这在个前提下，尽量降低时间和空间复杂度。</p>
        </section>	 
		
		<section>
            <h3>2.知识剖析</h3>
        </section>	 

        <section>
			<h4>FISHER–YATES SHUFFLE</h4>		
			<p>其算法思想就是 从原始数组中随机抽取一个新的元素到新数组中</p>
            <p>1.从还没处理的数组中，产生一个[0, n]之间的随机数 random</p>
			<p>2.从剩下的n个元素中把第 random 个元素取出到新数组中</p>
			<p>3.删除原数组第random个元素</p>
			<p>4.重复第 2 3 步直到所有元素取完</p>
			<p>5.最终返回一个新的打乱的数组</p>			
        </section>

        <section>
			<h4>KNUTH-DURSTENFELD SHUFFLE</h4>		
			<p>每次从未处理的数组中随机取一个元素，然后把该元素放到数组的尾部，即数组的尾部放的就是已经处理过的元素，这是一种原地打乱的算法，每个元素随机概率也相等，时间复杂度从 Fisher 算法的 O(n2)提升到了 O(n)</p>
            <p>1.选取数组(长度n)中最后一个元素(arr[length-1])，将其与n个元素中的任意一个交换，此时最后一个元素已经确定</p>
			<p>2.选取倒数第二个元素(arr[length-2])，将其与n-1个元素中的任意一个交换</p>
			<p>3.重复第 1 2 步，直到剩下1个元素为止</p>		
        </section>			

		<section>
		    <h4>INSIDE-OUT ALGORITHM</h4>
            <p>Knuth-Durstenfeld Shuffle 是一个in-place算法，原始数据被直接打乱，有些应用中可能需要保留原始数据，因此需要开辟一个新数组来存储打乱后的序列。 Inside-Out Algorithm 算法的基本思想是设一游标i从前向后扫描原始数据的拷贝，在[0, i]之间随机一个下标j，然后用位置j的元素替换掉位置i的数字，再用原始数据位置i的元素替换掉拷贝数据位置j的元素。其作用相当于在拷贝数据中交换i与j位置处的值。</p>			
        </section>		
      		
	    <section>
            <h3>3.常见问题</h3>
        </section>
		
        <section>
            <h4>Fisher–Yates Shuffle是如何实现的？</h4>
        </section>
		        		
        <section>
            <h3>4.解决方案</h3>
        </section>
		
        <section>
		    <h4>FISHER–YATES SHUFFLE的JS实现</h4>
        </section>
		
		<section>
		    <p>shuffle 函数挂载在 Array 对象的原型之下，便于数组直接调用该函数。在 shuffle 函数内部，this 引用的就是调用该 shuffle 的数组。 用一个新的变量引用 this，也就是调用 shuffle 函数的数组。接下来的for循环用于遍历所有数组内的所有元素，并进行随机交换。 注意，遍历顺序是从后往前进行的，也就是说从 input.length-1 位置的元素开始，直到遍历到数组中的第一个元素。遍历过程中的位置由变量 i 指定。 接下来，使用了两行代码在指定范围内挑选一个随机元素。 变量randomIndex存储了一个随机数，该随机数可以用作数组的索引，进而提取一个随机元素。注意，该随机数的最大值并不是数组的长度，而是变量i的值。 确定了随机元素的索引之后，用新的变量保存该元素的值，然后交换选中元素和随机元素的值。</p>
		</section>		

        <section>
            <h3>5.编码实战</h3>
        </section>

        <section>
        	<h3>6.扩展思考</h3>                
        </section>
		
        <section>
            <h4>怎么保证这个算法得到的数组是完全随机的（即等概）？</h4>			
		</section>
		
		<section>
            <h4>使用程序得到的一般是伪随机数</h4>		
            <p>笔者目前了解到最优秀的是梅森旋转算法，其在低于623次元的空间以内不存在线性回归，但仍然是一个伪随机算法。</p>			
		</section>
			
        <section>
            <h3>7.参考文献</h3>          
            <p>http://blog.csdn.net/robinjwong/article/details/18261393</p>
			<p>https://www.tuicool.com/articles/qIjqQzb</p>
        </section>
		
        <section>
            <h3>8.更多讨论</h3>
            <p>还有没有更简单的洗牌算法</p>	
        </section>
				
        <section>
            <h4>谢谢观看</h4>
            <p></p>
            <p><small>By:冯亚超</small></p>
        </section>


    </div>
</div>

<script src="https://ptteng.github.io/PPT/lib/reveal/js/head.min.js"></script>
<script src="https://ptteng.github.io/PPT/lib/reveal/reveal.js"></script>

<script>
    // 以下为常见配置属性的默认值
    // {
    //  controls: true, // 是否在右下角展示控制条
    //  progress: true, // 是否显示演示的进度条
    //  slideNumber: false, // 是否显示当前幻灯片的页数编号，也可以使用代码slideNumber: 'c / t' ，表示当前页/总页数。
    //  history: false, // 是否将每个幻灯片改变加入到浏览器的历史记录中去
    //  keyboard: true, // 是否启用键盘快捷键来导航
    //  overview: true, // 是否启用幻灯片的概览模式，可使用"Esc"或"o"键来切换概览模式
    //  center: true, // 是否将幻灯片垂直居中
    //  touch: true, // 是否在触屏设备上启用触摸滑动切换
    //  loop: false, // 是否循环演示
    //  rtl: false, // 是否将演示的方向变成RTL，即从右往左
    //  fragments: true, // 全局开启和关闭碎片。
    //  autoSlide: 0, // 两个幻灯片之间自动切换的时间间隔（毫秒），当设置成 0 的时候则禁止自动切换，该值可以被幻灯片上的 ` data-autoslide` 属性覆盖
    //  transition: 'default', // 切换过渡效果，有none/fade/slide/convex/concave/zoom
    //  transitionSpeed: 'default', // 过渡速度，default/fast/slow
    //  mouseWheel: true, //是否启用通过鼠标滚轮来切换幻灯片
    // }
    // 初始化幻灯片
    Reveal.initialize({
        history: true,
        dependencies: [
            { src: 'https://ptteng.github.io/PPT/plugin/markdown/marked.js' },
            { src: 'https://ptteng.github.io/PPT/plugin/markdown/markdown.js' },
            { src: 'https://ptteng.github.io/PPT/plugin/notes/notes.js', async: true },
            { src: 'https://ptteng.github.io/PPT/plugin/highlight/highlight.js', async: true, callback: function() { hljs.initHighlightingOnLoad(); } }
        ]
    });
</script>
</body>
</html>
